home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_08 / qcreg.cpp < prev    next >
C/C++ Source or Header  |  1992-07-11  |  20KB  |  645 lines
  1. ///////////////////////////////////////////////////////
  2. //  Listing 2 - QCREG.CPP: Quadcode region support
  3. //  Written by:
  4. //    Kenneth Van Camp
  5. //    RR #1 Box 1255
  6. //    East Stroudsburg, PA  18301
  7. //    (717)223-8620
  8. //
  9. //  Functions -
  10. //    Region::Region            construct from outline
  11. //    Region::ScanOutAET        create qc's in row
  12. //    Region::AddRow            add a row of qc's
  13. //    Region::AddQC             add a single qc
  14. //    Region::~Region           destructor
  15. //    Region::Compress          compress the region
  16. //    Region::InRegion          is qc within region?
  17. //    Region::MaxQuits          find max #quits
  18. //    Region::NumQC             find # qc's in region
  19. //    operator<<                region "put to" stream
  20. //    BuildGET                  build global edge table
  21. //    MoveJSortedToAET          move row GET to AET
  22. //    JSortAET                  sort AET by column
  23. //    AdvanceAET                advance edges in AET
  24. //    SetRegionYieldFunc        set appl. yield func
  25. //    DefaultRegionYieldFunc    the default yield func
  26. //
  27. ///////////////////////////////////////////////////////
  28.  
  29. #include <stdio.h>
  30. #include <stdlib.h>
  31. #include <string.h>
  32. #include <limits.h>
  33. #include <assert.h>
  34. #ifdef __TURBOC__
  35. #include <iostream.h>
  36. #else
  37. #include <stream.hpp>
  38. #endif
  39. #include "qc.h"
  40.  
  41. #define SWAP(a,b) { temp = a; a = b; b = temp; }
  42.  
  43. // Following class and globals are used locally,
  44. // for construction of regions:
  45.  
  46. // struct EdgeState: Holds data on edges of one row of
  47. // the polygon (region) during construction.
  48. struct EdgeState
  49. {
  50.   struct EdgeState  *next_edge;
  51.   COORD j,
  52.         start_i;
  53.   int   whole_pixel_jmove,
  54.         jdirection;
  55.   COORD error_term,
  56.         error_term_adj_up,
  57.         error_term_adj_down,
  58.         count;
  59. };
  60.  
  61. static EdgeState  *GETptr,      // Global edge table
  62.                   *AETptr;      // Active edge table
  63.  
  64. // This sets up the yield function, to allow yielding
  65. // to the user or another application:
  66. int DefaultRegionYieldFunc (int pct_complete);
  67. static int (*RegionYieldFunc) (int) = DefaultRegionYieldFunc;
  68.  
  69. // Local function prototypes:
  70. static void BuildGET (PointListHeader &vertex_list,
  71.     EdgeState *next_free_edge, COORD &min_i, COORD &max_i);
  72. static void MoveJSortedToAET (COORD i_to_move);
  73. static void JSortAET (void);
  74. static void AdvanceAET (void);
  75.  
  76. ///////////////////////////////////////////////////////
  77. // Region::Region: Constructor for region given a
  78. // perimeter list.  The following code is based on a
  79. // complex polygon fill routine by Michael Abrash, as
  80. // published in his Graphics Programming column in
  81. // Dr. Dobb's Journal, June 1991, pp. 139-143, 154-157.
  82. //   This function will periodically yield control to the
  83. // designated yield function.  If the yield function
  84. // returns TRUE, then region building is aborted and a
  85. // flag is set so that subsequent calls to NumQC() will
  86. // return a 0.
  87.  
  88. Region::Region (PointListHeader &vertex_list)
  89. // vertex_list  is an array of points describing the
  90. //              outline of the region.  The path is
  91. //              automatically closed from the last to
  92. //              the first point.
  93. {
  94.   first_qcnode = NULL;
  95.   aborted = FALSE;
  96.  
  97.   ndiv = vertex_list.ndiv;
  98.   int nquits = MaxQuits();
  99.   assert (nquits > 0);
  100.   // Reject polygons that are invisible.
  101.   assert (vertex_list.length >= 3);
  102.  
  103.   // Get enough memory to store entire edge table:
  104.   EdgeState *edge_table_buf;
  105.   edge_table_buf = new EdgeState[vertex_list.length];
  106.   assert (edge_table_buf != NULL);
  107.  
  108.   // Build the global edge table:
  109.   BuildGET (vertex_list, edge_table_buf, min_i, max_i);
  110.  
  111.   // Scan down through polygon edges, one scan line at
  112.   // a time, so long as at least one edge remains in
  113.   // either the GET or AET.
  114.   // Initialize the active edge table to empty:
  115.   AETptr = NULL;
  116.   // Start at the top polygon vertex.
  117.   current_i = GETptr->start_i;
  118.   int nqc_compress = 0; // qc's added since compression
  119.   while ((GETptr != NULL) || (AETptr != NULL))
  120.   {
  121.     // Update AET for this scan line.
  122.     MoveJSortedToAET (current_i);
  123.     // Add quadcodes for this scan line.
  124.     ScanOutAET (current_i, nqc_compress, nquits);
  125.     // Advance AET edges one scan line.
  126.     AdvanceAET();
  127.     // Re-sort on J.
  128.     JSortAET();
  129.     // Advance to next scan line.
  130.     current_i--;
  131.  
  132.     // Single compression pass after 100 quadcodes
  133.     if (nqc_compress > 100)
  134.     {
  135.       nqc_compress = 0;
  136.       (void)Compress();
  137.     }
  138.  
  139.     // Yield to the user or another application after each
  140.     // scan line:
  141.     if (RegionYieldFunc (PctComplete()))
  142.     {
  143.       // The process has been aborted.
  144.       // Set a flag, release dynamic memory, and return.
  145.       aborted = TRUE;
  146.       delete edge_table_buf;
  147.       return;
  148.     }
  149.  
  150.   }
  151.  
  152.   // Release dynamic memory
  153.   delete edge_table_buf;
  154.  
  155.   // Final compression, until nothing more to compress:
  156.   while (Compress())
  157.     ;
  158.  
  159. } // Region::Region
  160.  
  161. ///////////////////////////////////////////////////////
  162. // Region::ScanOutAET: Create quadcodes along an entire
  163. // row, using the odd/even fill rule.
  164.  
  165. void Region::ScanOutAET
  166.     (COORD i_to_scan, int &nqc_compress, int nquits)
  167. // i_to_scan    is the row # to scan
  168. // nqc_compress is the # qc's added since last compress
  169. // nquits       is the # of quits to use in each qc
  170. {
  171.   // Scan through AET, filling areas along current row
  172.   // as each pair of edge crossings is encountered.
  173.   // Nearest pixel on or to the right of left edges is
  174.   // drawn, and nearest pixel to the left of but not on
  175.   // the right edges is drawn.
  176.   EdgeState *current_edge = AETptr;
  177.   while (current_edge != NULL)
  178.   {
  179.     COORD left_j = current_edge->j;
  180.     current_edge = current_edge->next_edge;
  181.     AddRow (i_to_scan, left_j, current_edge->j - 1,
  182.         nquits);
  183.     nqc_compress += abs (current_edge->j - left_j);
  184.     current_edge = current_edge->next_edge;
  185.   }
  186. } // Region::ScanOutAET
  187.  
  188. ///////////////////////////////////////////////////////
  189. // Region::AddRow: Add an entire row of quadcodes.
  190.  
  191. void Region::AddRow
  192.     (COORD i, COORD j1, COORD j2, int nquits)
  193. // i        is the I coordinate of the row
  194. // j1       is the J coordinate at one end of the row
  195. // j2       is the J coordinate at other end of the row
  196. // nquits   is the # quits in the quadcode to add
  197. {
  198.   COORD j;
  199.   COORD jmin = min (j1, j2);
  200.   COORD jmax = max (j1, j2);
  201.  
  202.   for (j = jmax; j >= jmin; j--)
  203.     AddQC (i, j, nquits);
  204. } // Region::AddRow
  205.  
  206. ///////////////////////////////////////////////////////
  207. // Region::AddQC: Add a single quadcode to a region.
  208.  
  209. void Region::AddQC (COORD i, COORD j, int nquits)
  210. // i        is the I coordinate of the quadcode
  211. // j        is the J coordinate of the quadcode
  212. // nquits   is the # quits in the quadcode to add
  213. {
  214.   QCNode  *new_qcn = new QCNode (i, j, nquits);
  215.   assert (new_qcn != NULL);
  216.  
  217.   // Insert into linked list in sorted order.
  218.   QCNode  *qcn,
  219.           *prev = NULL;
  220.  
  221.   for (qcn = first_qcnode; qcn; qcn = qcn->next)
  222.   {
  223.     if (*new_qcn <= *qcn)
  224.     {
  225.       // Found insertion point
  226.       if (*new_qcn == *qcn)
  227.       {
  228.         // Quadcode already in list - don't add again.
  229.         delete new_qcn;
  230.         return;
  231.       }
  232.       break;
  233.     }
  234.     prev = qcn;
  235.   } // for qcn
  236.  
  237.   new_qcn->next = qcn;
  238.   if (prev)
  239.     prev->next = new_qcn;
  240.   else
  241.     // Add to head of list
  242.     first_qcnode = new_qcn;
  243.  
  244. } // Region::AddQC
  245.  
  246. ///////////////////////////////////////////////////////
  247. // Region::~Region: Region destructor
  248.  
  249. Region::~Region (void)
  250. {
  251.   QCNode  *qcn,
  252.           *nextqcn;
  253.  
  254.   // Release the linked list of quadcode nodes
  255.   for (qcn = first_qcnode; qcn; qcn = nextqcn)
  256.   {
  257.     nextqcn = qcn->next;
  258.     delete qcn;
  259.   }
  260.   first_qcnode = NULL;
  261. } // Region::~Region
  262.  
  263. ///////////////////////////////////////////////////////
  264. // Region::Compress: This function makes a single pass
  265. // at compressing a region, by finding any four consec-
  266. // utive quadcodes that are siblings and replacing them
  267. // with their parent.  Return TRUE if any compression
  268. // took p